Data compression or source coding techniques are useful in reducing the volume of data generated by a source for the purpose of storage or transmission. Economies are realized when the volume of data to be transmitted or stored is decreased. There are two kinds of data compression techniques; namely, information preserving and information degrading. A process is information preserving (lossless) if all the information present before coding can be regenerated after coding. Conversely, a process is information degrading (lossy) if it is irreversible in the sense that the original information cannot be regenerated exactly after the process is performed. An information degrading process can be used when the user of the information is not interested in all the information generated by the source. If the user is only selectively interested in the information, the information degrading coding process can reflect that selectivity. Also, if the user is willing to accept a fidelity criterion, the data may be degraded within certain limits and still remain useful. In general, more data compression can be obtained with information degrading processes than with information preserving processes.
Source coding systems can be classified as statistical or ad hoc, depending on whether or not the system is in some sense optimal in terms of Shannon's noiseless coding theorem. An optimal noiseless coding scheme is one where the average codeword length equals the entropy per symbol of the source. Schemes where the average codeword length achieves or approaches closely the minimum of the entropy are herein referred to as "entropy-coding" schemes. Entropy-coding is well known in the art, e.g., reference A. Gersho and R. M. Gray, Vector Quantization and Signal Compression, Kluwer Academic Publishers, Norwell, Mass. (1992). A final classification of source coding systems is the following: if the system accepts digits from the source in fixed length blocks and then generates a variable length sequence of encoded digits, the system is "block-to-variable"; while if the system accepts a variable length sequence of digits from the source and generates a fixed length block of digits, the system is "variable-to-block".
A first optimal coding scheme to be developed was Huffman coding. The technique is block-to-variable. Huffman coding specifies the optimal coding for M messages with probabilities p.sub.1,p.sub.2, . . . ,P.sub.M, where p.sub.i is the probability that message "i" is emitted. The least probable message is assigned a codeword containing the longest sequence of bits and more probable messages are assigned codewords of shorter length. In an ideal code, the binary codeword length for message "i" is log.sub.2 (1/p.sub.i). When Huffman coding is applied to a binary source, the source sequence may be broken up into blocks n bits long. Each block then contains one of M=2.sup.n possible messages. For a source with K possible symbols, the number of possible messages in a block of length n is M=K.sup.n. As n gets large it becomes impractical to calculate the probability of each message and to generate the corresponding codeword. However, Huffman coding is only optimal as n approaches infinity. Furthermore, this coding scheme requires knowledge of the source statistics and the codewords must be computed a priori. The codewords must be stored in the memory of the encoder and a table look-up is performed on each block. The memory requirements grow exponentially with n. In short, complexity and required knowledge of the source statistics detract from the desirability of Huffman coding.
Another so-called entropy code is the arithmetic code. In arithmetic coding, a long sequence of source symbols is associated with a unique interval of real numbers between 0 and 1. A finite length binary sequence, corresponding to a binary fraction of a number inside that interval, becomes the codeword for the sequence of source symbols. In general, an arithmetic code is slower and harder to implement than a Huffman code, but generally achieves slightly better compression performance for long symbol sequences. In the arithmetic code, a codeword is found by a sequential set of calculations as each symbol from the sequence is received. Therefore, unlike the Huffman code, a codeword is not stored for every possible source sequence. However, the conditional probabilities of the possible current symbols, given the past symbols, must either be calculated or stored beforehand, or a combination thereof, in finding the interval and binary fraction for the particular source sequence. This memory/computation requirement for the arithmetic code is of the same order as the memory requirement of the Huffman code. In general, an arithmetic code is slower and harder to implement than a Huffman code, but generally achieves slightly better compression performance for long symbol sequences.
Run length coding is an ad hoc coding scheme that works well when the probability of a certain symbol from the source is very high (i.e., close to one). In a simple implementation with a binary source, where the probability of a zero is high, the number of consecutive zeroes is counted. When the first "1" is encountered, the number of zeroes is transmitted as a fixed-length block of binary digits. Thus, run length coding is variable-to-block and this fact simplifies the code work considerably. However, the run length digits are not equally probable, and they are often encoded with an entropy code (e.g., Huffman or arithmetic code) to obtain better compression. Also, run length coding is limited by the fact that it is reasonably efficient only when the probability of some source symbol is high and even in this case it is not optimal.
To summarize, the above approaches comprise certain well known source coding schemes, the data compression field, however, is replete with additional coding schemes.
In practical applications of waveform coding, a common rule is that sources have characteristics which continually change. These changes can be easy to identify, like activity in voice coding, or more subtle such as textures and images or instrument timbre in music. The simplest coding methods are known to be ideal under conditions like stationarity, which may be too far from reality. Conversely, there exist many methods for complex sources, e.g., non-stationary, but such methods typically are computationally complex. Frequently, an, exponential growth in complexity makes implementation impractical.
Therefore, an important problem for waveform coding is to devise efficient coding schemes that are highly adaptive, yielding good results for changing source characteristics, and which at the same time have complexity consistent with a particular application, such as real time coding. Many of the most effective algorithms now appearing in the literature employ coding algorithms with intelligent rules for detecting patterns in the source or some form of source state. However, these prior solutions are typically constrained to a single type of source.
Generally, data compression is more efficient as more samples of the source data stream are coupled together. However, the number of possible sequences of sample values grows exponentially with the group size. Even for four samples from a gray-scale image of 256 levels (i.e., the alphabet), the number of distinct sequences of four values (called the alphabet extension) is over four billion, which is too high to be treated by known methods of optimal compression wherein a binary codeword is associated with each one of the possibilities.
Thus, the present invention seeks to provide a novel method for compressing data, and in particular, groups of samples by reducing the number of possibilities through alphabet and sample-set partitioning, while still achieving nearly optimal data compression.